The present invention relates to searching for a value in a multi-level table.
Routers route network packets based on network address information that is embedded in the headers of the packets. For example, referring to FIG. 1, in an Internet Protocol (IP) network 10 such as the Internet, end stations ES1, ES2, and ES3 are connected to routers R1, R4, and R5, respectively. End stations E1, E2, and E3 may each be, for example, a client or a server. Each of the routers in the network 10 is connected to one or more other routers. Each stream of information transmitted from one end station to another is broken into packets containing, among other things, a destination address indicating the end station to which the packet should be delivered.
A packet is transmitted from one end station to another via a sequence of routers. For example, a packet may originate at end station ES1, traverse routers R1, R2, R3, and R4, and then be delivered to end station ES2. Each router has access to information about each of the nodes to which the router is connected. When a router receives a packet, the router examines the packet""s destination address and forwards the packet to a node that the router calculates to be most likely to bring the packet closer to its destination address. The process of choosing an intermediate destination for a packet and forwarding the packet to the intermediary destination is called routing.
The main step performed by a router is to look up the destination address of each incoming packet in a table called a routing table in order to determine to which router or end station the packet should be forwarded.
An IP router""s routing table contains records which each associate an IP address xe2x80x9cprefixxe2x80x9d with an output link of the router. For this reason the routing table of an IP router will also be referred to as a xe2x80x9cprefix databasexe2x80x9d herein. A prefix is a sequence of bits representing the most significant bits of an IP address, such as the portion of an IP address corresponding to a second-level domain. When an IP router receives a packet, it identifies the longest prefix in the routing table that matches the beginning of the packet""s destination address. The router then sends the packet to the router output link associated with the identified prefix, thereby forwarding the packet to another router or to the packet""s destination end station (the xe2x80x9cnext hopxe2x80x9d in the network).
For example, if a routing table contains the prefixes P1=0101, P2=0101101, and P3=010110101011, the longest matching prefix for a destination address whose first 12 bits are 010101101011 is the prefix P1. The longest matching prefix for a destination address whose first 12 bits are 010110101101 is the prefix P3. The process of finding the longest matching prefix for a destination address is called lookup.
In one aspect, the invention features a device for identifying an item that is an optimal match for a search key. The device includes a first search stage, which includes an input for receiving a signal corresponding to a first part of the search key, a first output for developing a first control signal indicating whether the item can be identified from the first part of the search key, and a second output for developing a first item identifier signal identifying the item if the item can be identified from the first part of the search key and for developing a second control signal if the item cannot be identified from the first part of the search key. The device also includes a second search stage for identifying the item based on the second control signal and a second part of the search key, including a first input coupled to the second output of the first search stage, a second input for receiving a signal corresponding to the second part of the search key, and a first output for developing a second item identifier signal identifying the item. The device also includes a demultiplexor for selecting a select one of the first item identifier signal and the second item identifier signal based on the first control signal.
The item may correspond to a range of Internet Protocol (IP) addresses. The item may be an the item comprises an IP address prefix. The range of addresses may include addresses corresponding to multiple IP address prefixes. The search key may be a destination IP address. The item that is the optimal match for the search key may be the longest prefix in a prefix database that matches the search key. The first part of the search key may be a contiguous sequence of bits in the destination address. The second part of the identifier may be a contiguous sequence of bits in the destination address.
The first search stage may be a first search table memory. The first search table memory may store a first search table, wherein entries in the first search table correspond to ranges of Internet Protocol addresses, some entries in the first search table store prefix identifiers for developing the first item identifier signal, and some entries store second search stage identifiers for developing the second control signal.
The second search stage may be a second search table memory, and the second control signal may be an addressing signal for partially addressing the second search table memory. The second search table memory may store a second search table, entries in the second search table corresponding to ranges of Internet Protocol addresses, the entries storing prefix identifiers for developing the second item identifier signal.
The device may include default memories for storing default values of items. The demultiplexor may include a first control input coupled to the first output of the first search stage, a first data input coupled to the second output of the first search stage, and a second data input coupled to the output of the second search stage. The demultiplexor may select the first prefix identifier signal if the first control signal indicates that the prefix can be identified from the first part of the destination address, and may select the second prefix identifier signal otherwise.
The second search stage of the device may operate simultaneously with the first search stage.
In another aspect, the invention features a computer-implemented method for searching a multi-level search table for a best-matching item identifier specifying an item corresponding to a search key. An entry in a first level of the search table corresponding to the search key is identified. If the entry contains an item identifier, the item identifier is identified as the best-matching item identifier. Otherwise, a subsequent level of the multi-level search table is searched for the best-matching item identifier using information associated with the entry that is descriptive of the subsequent level and of a first default value.
Searching the subsequent level of the multi-level search table may result in information descriptive of a second default value, in which case the second default value is replaced with the first default value.
The item may be a prefix of an IP address. The search key may be an IP address. The information contained in the entry may identify a part of the subsequent level of the multi-level search table corresponding to the destination address. The part may be a sub-table of the subsequent level of the multi-level search table. The part may be an entry of the subsequent level of the multi-level search table.
Entries in the multi-level search table may correspond to ranges of Internet Protocol addresses. If a prefix database contains a prefix corresponding to all Internet Protocol addresses within a range, then an entry in the search table corresponding to the range identifies the prefix. Otherwise, the entry in the search table corresponding to the range identifies a part of a subsequent level of the search table corresponding to the destination address. If the entry indicates a default item identifier, a default item identifier corresponding to the search key is idenfitied as the best-matching item identifier.
The item may be a prefix of an Internet Protocol address, and the search key may be an Internet Protocol address. The default item identifier may be stored in a table of default item identifiers, and the default item identifier may be located in the table of default item identifiers using the search key. An exception may be generated if the item identifier is associated with exception information descriptive of the search key.
In another aspect, the invention features a data structure tangibly stored on a computer-readable medium, the data structure representing a multi-level search table for identifying a best-matching prefix identifier identifying a prefix corresponding to a destination address. The data structure includes a plurality of levels of search tables, entries of the search tables corresponding to ranges of Internet Protocol addresses. If a prefix database contains a prefix corresponding to all Internet Protocol addresses within a range, then an entry in the search table corresponding to the range identifies the prefix. Otherwise, the entry in the search table corresponding to the range identifies a part of a subsequent level of the search table corresponding to the destination address. The data structure further includes a plurality of levels of default prefix tables, entries of the default prefix tables corresponding to default prefixes for ranges corresponding to entries in the search tables.
If a prefix corresponding to all and only all of the addresses within the range is contained in a prefix database, then the default prefix of the range is the prefix. Otherwise, the default prefix of the range is the first prefix in the prefix database that is less specific than the prefix.
In another aspect, the invention features a computer-implemented method for updating a multi-level search table in response to addition of an item to an item database, the item corresponding to a level of the multi-level search table. The level of the search table is updated and a default table corresponding to the level of the search table is updated.
The item may be an Internet Protocol address prefix, and the search key may be an Internet Protocol address. Entries in the default table may correspond to ranges of Internet Protocol addresses corresponding to the level of the search table, and entries of the default table may contain default prefixes for the ranges of Internet Protocol addresses. Entries of a first level of the multi-level search table may contain a default value, and other levels of the multi-level search table may contain a default value designator. Updating may be pipelined.
In another aspect, the invention features a computer-implemented method for updating a multi-level search table in response to deletion of an item from an item database, the item corresponding to a level of the multi-level search table. The level of the search table is updated and a default table corresponding to the level of the search table is updated.
The item may be an Internet Protocol address prefix and the search key may be an Internet Protocol address. Entries in the default table may correspond to ranges of Internet Protocol addresses corresponding to the level of the search table, and entries of the default table may contain default prefixes for the ranges of Internet Protocol addresses. Entries of a first level of the multi-level search table may contain a default value, and other levels of the multi-level search table may contain a default value designator. Updating may be pipelined. Detection of whether the prefix is the only prefix in the item database that is more specific than a range of Internet Protocol addresses corresponding to an entry in the multi-level search table may be performed.
Among the advantages of the invention are one or more of the following.
One advantage of the invention is that the size of the multi-level search table varies linearly with the size of the pattern database to which it corresponds. This results in the ability to maintain search tables for very large pattern databases at a cost that varies linearly with the size of the pattern database.
Another advantage of the invention is that searches performed using the multi-level search table can be performed very quickly, for example, at speeds of 100,000,000 searches per second using SRAM technology currently available or at speeds of 10,000,000 lookups per second using DRAM technology currently available. Furthermore, if pipelining is used, the speed at which searches are performed does not noticeably increase as the number of levels in the search table is increased.
Another advantage of the invention is that search table update operations can be performed in an incremental manner, allowing search table update operations to be interleaved with search operations. This eliminates service interruptions due to the need to wait for completion of updates before searching can be resumed. Furthermore, because search operations can be performed while search memory is being updated, it is not necessary to maintain multiple copies of search memory in order to interleave update operations with search operations.
Another advantage of the invention is that the rate at which searches are performed is uniform and predictable, regardless of the particular distribution of patterns in the pattern database and of the nature of the search requests.
Another advantage of the invention is that it does not require that the entire search table be re-generated in response to changes to the prefix database. Rather, when a prefix is added to or deleted from the prefix database, only those parts of the search table that are affected by the change to the prefix database are updated.
Another advantage of the invention is that the methods of searching and updating the search table are particularly well suited for use in systems such as IP networks, where the length of the patterns (e.g., prefixes) in the pattern database varies. For example, under IPv4, prefix lengths vary from 8 to 32 bits, and under IPv6, prefix lengths vary from 16 to 64 bits.
Another advantage of the invention is that the use of default prefix tables simplifies the process of updating the multi-level search table and therefore increases the speed with which the table can be updated. Furthermore, the use of default prefix tables simplifies the update machinery, allowing updates to be limited to a single stage of the search device. Additionally, because default prefix tables reduce the complexity of update operations and increase the speed at which updates can be performed, the degree to which search operations are interrupted by update operations is greatly reduced.
The techniques described below may be implemented in computer hardware or software, or a combination of the two. However, the techniques are not limited to any particular hardware or software configuration; they may find applicability in any computing or processing environment that may be used for searching a multi-level table for a value. The techniques may be implemented in computer programs executing on programmable computers that each include a processor, a storage medium readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code is applied to data entered using the input device to perform the functions described and to generate output information. The output information is applied to the one or more output devices.
Each process described herein may be implemented, for example, in a high level procedural or object oriented programming language to communicate with a computer system. However, the programs can be implemented in assembly or machine language, if desired. In any case, the language may be a compiled or interpreted language.
Each such computer program may be stored on a storage medium or device (e.g., CD-ROM, hard disk or magnetic diskette) that is readable by a general or special purpose programmable computer for configuring and operating the computer when the storage medium or device is read by the computer to perform the procedures described in this document. The system may also be considered to be implemented as a computer-readable storage medium, configured with a computer program, where the storage medium so configured causes a computer to operate in a specific and predefined manner.
Other features and advantages of the invention will become apparent from the following description and from the claims.